/**
 * 6075. 装满石头的背包的最大数量
 * https://leetcode.cn/contest/weekly-contest-294/problems/maximum-bags-with-full-capacity-of-rocks/
 */

/**
 * @param {any[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[]} capacity
 * @param {number} length
 */
function resolve(capacity, length) {
  if (length <= 1) {
    return;
  }
  for (let root = Math.floor(length / 2 - 1); root >= 0; root -= 1) {
    const rootVal = capacity[root];
    const left = root * 2 + 1;
    const leftVal = capacity[left];
    const right = left + 1;
    const rightVal = right >= length ? Infinity : capacity[right];
    if (rootVal > leftVal || rootVal > rightVal) {
      if (leftVal <= rightVal) {
        swap(capacity, root, left);
      } else {
        swap(capacity, root, right);
      }
    }
  }
}

/**
 * @param {number[]} capacity
 * @param {number[]} rocks
 * @param {number} additionalRocks
 * @return {number}
 */
function maximumBags(capacity, rocks, additionalRocks) {
  for (let i = 0; i < capacity.length; i += 1) {
    capacity[i] -= rocks[i];
  }
  let count = 0;
  let { length } = capacity;
  let rest = additionalRocks;
  while (length) {
    resolve(capacity, length);
    const [c] = capacity;
    if (rest < c) {
      break;
    }
    rest -= c;
    swap(capacity, 0, length - 1);
    count += 1;
    length -= 1;
  }
  return count;
}

console.log(maximumBags([2, 3, 4, 5], [1, 2, 4, 4], 2) === 3);
console.log(maximumBags([10, 2, 2], [2, 2, 0], 100) === 3);
